package structures.sort;

import java.util.Arrays;

// 基数排序
public class RadixSortDemo {

    private static final int LENGTH = 10000;

    public static void main(String[] args) {
        // 生成数据
        int[] data = new int[LENGTH];
        for (int index = 0; index < data.length; index++) {
            data[index] = (int) (Math.random() * LENGTH);
        }
        System.out.println(Arrays.toString(data));

        // 排序
        long startTime = System.currentTimeMillis();
        radixSort(data);
        System.out.println("----------------消耗时间: " + (System.currentTimeMillis() - startTime) + " ms------------");

        System.out.println(Arrays.toString(data));

    }

    private static void radixSort(int[] data) {
        int[][] bucket = new int[10][data.length];
        int[] bucketIndex = new int[10];

        int maxValue = data[0];
        for (int index = 0; index < data.length; index++) {
            if (maxValue < data[index]) {
                maxValue = data[index];
            }
        }

        int dataIndex = 0;
        // 按照最大数决定遍历次数
        for (int i = 0; i < String.valueOf(maxValue).length(); i++) {
            // 遍历元素
            for (int index = 0; index < data.length; index++) {
                int digitOfElement;
                if (i == 0) {
                    digitOfElement = data[index] % 10;
                } else {
                    digitOfElement = (data[index] / ((int) Math.pow(10, i))) % 10;
                }
                bucket[digitOfElement][bucketIndex[digitOfElement]++] = data[index];
            }

            // 把数据放到原数组中
            dataIndex = 0;
            for (int index = 0; index < bucket.length; index++) {
                for (int j = 0; j < bucketIndex[index]; j++) {
                    data[dataIndex++] = bucket[index][j];
                }
            }
            // 清空index数组
            Arrays.fill(bucketIndex, 0);
        }



//        for (int index = 0; index < data.length; index++) {
//            int digitOfElement = data[index] / 10 % 10;
//            bucket[digitOfElement][bucketIndex[digitOfElement]++] = data[index];
//        }
//
//        dataIndex = 0;
//        for (int index = 0; index < bucket.length; index++) {
//            for (int i = 0; i < bucketIndex[index]; i++) {
//                data[dataIndex++] = bucket[index][i];
//            }
//        }

    }
}


